1

Minkowski Complexity of Sets: An Easy Lower Bound

Stasys Jukna,
Journal:
American Mathematical Monthly
Year:
2017
Language:
english
File:
PDF, 196 KB
english, 2017
2

Entropy of contact circuits and lower bounds on their complexity

Stasys P. Jukna
Journal:
Theoretical Computer Science
Year:
1988
Language:
english
File:
PDF, 2.02 MB
english, 1988
3

Combinatorics of Monotone Computations

Stasys Jukna
Journal:
Combinatorica
Year:
1999
Language:
english
File:
PDF, 304 KB
english, 1999
4

[Texts in Theoretical Computer Science. An EATCS Series] Extremal Combinatorics ||

Jukna, Stasys
Year:
2011
Language:
english
File:
PDF, 4.37 MB
english, 2011
5

On the optimality of Bellman–Ford–Moore shortest path algorithm

Jukna, Stasys, Schnitger, Georg
Journal:
Theoretical Computer Science
Year:
2016
Language:
english
File:
PDF, 342 KB
english, 2016
6

On set intersection representations of graphs

Stasys Jukna
Journal:
Journal of Graph Theory
Year:
2009
Language:
english
File:
PDF, 193 KB
english, 2009
8

Representing (0, 1)-matrices by boolean circuits

Stasys Jukna
Journal:
Discrete Mathematics
Year:
2010
Language:
english
File:
PDF, 328 KB
english, 2010
9

On the minimum number of negations leading to super-polynomial savings

Stasys Jukna
Journal:
Information Processing Letters
Year:
2004
Language:
english
File:
PDF, 147 KB
english, 2004
10

On the P versus NP intersected with co-NP question in communication complexity

Stasys Jukna
Journal:
Information Processing Letters
Year:
2005
Language:
english
File:
PDF, 77 KB
english, 2005
11

Linear codes are hard for oblivious read-once parity branching programs

Stasys Jukna
Journal:
Information Processing Letters
Year:
1999
Language:
english
File:
PDF, 309 KB
english, 1999
12

Entropy of Operators or why Matrix Multiplication is

Stasys Jukna
Journal:
Theory of Computing Systems
Year:
2010
Language:
english
File:
PDF, 284 KB
english, 2010
13

Expanders and time-restricted branching programs

Stasys Jukna
Journal:
Theoretical Computer Science
Year:
2008
Language:
english
File:
PDF, 431 KB
english, 2008
14

On multi-partition communication complexity

Pavol Ďuriš, Juraj Hromkovič, Stasys Jukna, Martin Sauerhoff, Georg Schnitger
Journal:
Information and Computation
Year:
2004
Language:
english
File:
PDF, 344 KB
english, 2004
15

Min-rank conjecture for log-depth circuits

Stasys Jukna, Georg Schnitger
Journal:
Journal of Computer and System Sciences
Year:
2011
Language:
english
File:
PDF, 277 KB
english, 2011
16

Cutting planes cannot approximate some integer programs

Stasys Jukna, Georg Schnitger
Journal:
Operations Research Letters
Year:
2012
Language:
english
File:
PDF, 211 KB
english, 2012
17

Yet harder knapsack problems

Stasys Jukna, Georg Schnitger
Journal:
Theoretical Computer Science
Year:
2011
Language:
english
File:
PDF, 242 KB
english, 2011
18

Clique problem, cutting plane proofs and communication complexity

Stasys Jukna
Journal:
Information Processing Letters
Year:
2012
Language:
english
File:
PDF, 160 KB
english, 2012
19

Disproving the Single Level Conjecture

Jukna, Stasys
Journal:
SIAM Journal on Computing
Year:
2006
Language:
english
File:
PDF, 218 KB
english, 2006
20

Limitations of Incremental Dynamic Programming

Stasys Jukna
Journal:
Algorithmica
Year:
2014
Language:
english
File:
PDF, 961 KB
english, 2014
22

Lower Bounds for Tropical Circuits and Dynamic Programs

Jukna, Stasys
Journal:
Theory of Computing Systems
Year:
2015
Language:
english
File:
PDF, 600 KB
english, 2015
23

Lower bounds for monotone counting circuits

Jukna, Stasys
Journal:
Discrete Applied Mathematics
Year:
2016
Language:
english
File:
PDF, 427 KB
english, 2016
24

Complexity of Linear Boolean Operators

Jukna, Stasys
Journal:
Foundations and Trends® in Theoretical Computer Science
Year:
2013
Language:
english
File:
PDF, 725 KB
english, 2013
25

Tropical Complexity, Sidon Sets, and Dynamic Programming

Jukna, Stasys
Journal:
SIAM Journal on Discrete Mathematics
Year:
2016
Language:
english
File:
PDF, 440 KB
english, 2016
26

Incremental versus non-incremental dynamic programming

Jukna, Stasys
Journal:
Operations Research Letters
Year:
2018
Language:
english
File:
PDF, 379 KB
english, 2018
27

Greedy can beat pure dynamic programming

Jukna, Stasys, Seiwert, Hannes
Journal:
Information Processing Letters
Year:
2019
Language:
english
File:
PDF, 210 KB
english, 2019
28

Approximation Limitations of Pure Dynamic Programming

Jukna, Stasys, Seiwert, Hannes
Journal:
SIAM Journal on Computing
Year:
2020
Language:
english
File:
PDF, 577 KB
english, 2020